package 二叉树;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class No297二叉树的序列化与反序列化 {

    /**
     * 序列化是将一个数据结构或者对象转换为连续的比特位的操作，
     * 进而可以将转换后的数据存储在一个文件或者内存中，
     * 同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
     * 请设计一个算法来实现二叉树的序列化与反序列化。
     * 这里不限定你的序列 / 反序列化算法执行逻辑，
     * 你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
     * 提示: 输入输出格式与 LeetCode 目前使用的方式一致，
     * 详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
     *
     * 示例 1：
     * 输入：root = [1,2,3,null,null,4,5]
     * 输出：[1,2,3,null,null,4,5]
     * 示例 2：
     * 输入：root = []
     * 输出：[]
     * 示例 3：
     * 输入：root = [1]
     * 输出：[1]
     * 示例 4：
     * 输入：root = [1,2]
     * 输出：[1,2]
     *  
     * 提示：
     * 树中结点数在范围 [0, 104] 内
     * -1000 <= Node.val <= 1000
     */

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {

        if(root==null){
            return null;
        }

        StringBuilder sb=new StringBuilder();
        LinkedList<TreeNode> queue=new LinkedList<>();

        queue.addLast(root);

        while (!queue.isEmpty()){

            int count=queue.size();

            while (count>0){

                TreeNode treeNode = queue.removeFirst();

                sb.append(treeNode==null?"x":treeNode.val);
                sb.append(",");

                if(treeNode!=null) {
                    queue.addLast(treeNode.left);
                    queue.addLast(treeNode.right);
                }

                count--;
            }

            //切除多余的 ","
            sb.deleteCharAt(sb.length()-1);
            //每层的断层,使用什么表达?使用@表达
            sb.append("@");

        }

        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        if(data==null){
            return null;
        }

        //根据层序遍历恢复二叉树
        String[] arr = data.split("@");

        LinkedList<TreeNode> lastQueue=new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
        lastQueue.addLast(root);
        LinkedList<TreeNode> currentQueue=new LinkedList<>();

        int index=1;//0层已经录入
        while (index<arr.length){

            //录入当前层的元素
            String[] splitArr = arr[index].split(",");
            int cIndex=0;

            while (!lastQueue.isEmpty()){
                TreeNode treeNode = lastQueue.removeFirst();
                if(treeNode==null){
                    continue;
                }
                treeNode.left=splitArr[cIndex].equals("x")?null:new TreeNode(Integer.parseInt(splitArr[cIndex]));
                cIndex++;
                treeNode.right=splitArr[cIndex].equals("x")?null:new TreeNode(Integer.parseInt(splitArr[cIndex]));
                cIndex++;
                currentQueue.addLast(treeNode.left);
                currentQueue.addLast(treeNode.right);
            }

            //当前这一层与上一层连接完成了
            lastQueue=new LinkedList<>(currentQueue);
            currentQueue.clear();
            index++;

        }

        return root;
    }

    public static void main(String[] args) {
        No297二叉树的序列化与反序列化 n=new No297二叉树的序列化与反序列化();
        TreeNode treeNode = TreeNode.getNodeByArr(new Integer[]{4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2});
        treeNode.printNode();
        String serializeStr = n.serialize(treeNode);
        System.out.println(serializeStr);
        TreeNode result = n.deserialize(serializeStr);
        result.printNode();
    }

}
